Monodigital Representations

Memory limit: 32 MB

Let be a decimal digit different from . We say that an arithmetic expression is a -representation of the integer if a value of this expression is and if it contains only numbers composed of a digit . (All the numbers are of course decimal). The following arithmetical operations are allowed in the expression: addition, subtraction, multiplication and division. Round brackets are allowed too. Division may appear only when a dividend is a multiple of a divisor.

Example

Each of the following expressions is the 5-representation of the number 12:

• 5+5+(5:5)+(5:5)
• (5+(5))+5:5+5:5
• 55:5+5:5
• (55+5):5

The length of the -representation is the number of occurrences of digit in the expression. In the example above the first two representations have the length 6, the third - 5, and the forth - 4.

Task

Write a program which:

• reads the digit and the series of numbers from the standard input,
• verifies for each number from the series, whether it has a -representation of length at most 8, and if it does, then the program finds the minimal length of this representation,
• writes results to the standard output.

Input

The first line of the standard input contains digit , is en element of . The second line contains number , . In the following lines there is the series of natural numbers , (for ), one number in each line.

Output

The standard output composes of lines. The -th line should contain:

• exactly one number which is the minimal length of -representation of , assuming that such a representation of length not grater then 8 exists,
• one word NIE (means 'no' in Polish), if the minimal length of the -representation of the number is grater than 8.

Example

For the input data:

5
2
12
31168

the correct result is:

4
NIE

Task author: Krzysztof Lorys.